package com.gitee.hellowllh.dlearn.algorithm.leetcode.basic.arrarys;

import cn.hutool.core.util.ArrayUtil;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

import java.util.Arrays;
import java.util.Collection;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;

/**
 * 搜索插入位置：
 *
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 * 示例 2:
 *
 * 输入: nums = [1,3,5,6], target = 2
 * 输出: 1
 * 示例 3:
 *
 * 输入: nums = [1,3,5,6], target = 7
 * 输出: 4
 * 示例 4:
 *
 * 输入: nums = [1,3,5,6], target = 0
 * 输出: 0
 * 示例 5:
 *
 * 输入: nums = [1], target = 0
 * 输出: 0
 *  
 *
 * 提示:
 *
 * 1 <= nums.length <= 104
 * -104 <= nums[i] <= 104
 * nums 为无重复元素的升序排列数组
 * -104 <= target <= 104
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-insert-position
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
@RunWith(Parameterized.class)
public class SearchInsertPosition {
    private int[] nums;
    private int target;
    private int out;

    public SearchInsertPosition(int[] nums, int target, int out) {
        this.nums = nums;
        this.target = target;
        this.out = out;
    }
    @Parameterized.Parameters
    public static Collection prepareData() {
        // 示例:
        Object[][] object = {
                { new int[]{ 1,3,5,6  }, 5, 2  } ,
                { new int[]{ 1,3,5,6  }, 2, 1  } ,
                { new int[]{ 1,3,5,6  }, 7, 4  } ,
                { new int[]{ 1,3,5,6  }, 0, 0  } ,
                { new int[]{ 1  }, 0, 0  }
        };
        return Arrays.asList(object);// 数组转化成集合形式。
    }


    @Test
    public void testOk() {
        // 注意是调用的成员变量。
        int i = this.searchInsert(this.nums,this.target);
        assertEquals(this.out,i);
    }

    public int searchInsert(int[] nums, int target) {
        // 二分查找法:
        int left = 0, right = nums.length-1;
        while(left <=  right ){
            int mid = (left + right) /2;
            if( nums[mid] == target ){
                right = mid -1 ; // find return.
            }else if ( nums[mid] < target  ){
                left = mid + 1;
            }else if( nums[mid] > target){
                right = mid -1;
            }
        }
        return left;
    }

    @Test
    public void testOk1() {
        // 注意是调用的成员变量。
        int i = this.searchInsert1(this.nums,this.target);
        assertEquals(this.out,i);
    }

    /**
     * @see <a href="https://leetcode-cn.com/problems/search-insert-position/solution/hua-jie-suan-fa-35-sou-suo-cha-ru-wei-zhi-by-guanp/">muban</a>
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert1(int[] nums, int target) {
        int left = 0, right = nums.length; // 注意
        while(left < right) { // 注意
            int mid = (left + right) / 2; // 注意
            if(nums[mid] == target) {
                // 相关逻辑
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1; // 注意
            } else {
                right = mid; // 注意
            }
        }
        // 相关返回值
        return left;
    }


    /**
     * 方法一：二分查找
     * 思路与算法
     *
     * 假设题意是叫你在排序数组中寻找是否存在一个目标值，那么训练有素的读者肯定立马就能想到利用二分法在 O(\log n)O(logn) 的时间内找到是否存在目标值。但这题还多了个额外的条件，即如果不存在数组中的时候需要返回按顺序插入的位置，那我们还能用二分法么？答案是可以的，我们只需要稍作修改即可。
     *
     * 考虑这个插入的位置 \textit{pos}pos，它成立的条件为：
     *
     * \textit{nums}[pos-1]<\textit{target}\le \textit{nums}[pos]
     * nums[pos−1]<target≤nums[pos]
     *
     * 其中 \textit{nums}nums 代表排序数组。由于如果存在这个目标值，我们返回的索引也是 \textit{pos}pos，因此我们可以将两个条件合并得出最后的目标：「在一个有序数组中找第一个大于等于 \textit{target}target 的下标」。
     *
     * 问题转化到这里，直接套用二分法即可，即不断用二分法逼近查找第一个大于等于 \textit{target}target 的下标 。下文给出的代码是笔者习惯的二分写法，\textit{ans}ans 初值设置为数组长度可以省略边界条件的判断，因为存在一种情况是 \textit{target}target 大于数组中的所有数，此时需要插入到数组长度的位置。
     *
     *
     * 1 / 15
     *
     * JavaC++JavaScriptCGolang
     *
     * class Solution {
     *     public int searchInsert(int[] nums, int target) {
     *         int n = nums.length;
     *         int left = 0, right = n - 1, ans = n;
     *         while (left <= right) {
     *             int mid = ((right - left) >> 1) + left;
     *             if (target <= nums[mid]) {
     *                 ans = mid;
     *                 right = mid - 1;
     *             } else {
     *                 left = mid + 1;
     *             }
     *         }
     *         return ans;
     *     }
     * }
     * 复杂度分析
     *
     * 时间复杂度：O(\log n)O(logn)，其中 nn 为数组的长度。二分查找所需的时间复杂度为 O(\log n)O(logn)。
     *
     * 空间复杂度：O(1)O(1)。我们只需要常数空间存放若干变量。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/search-insert-position/solution/sou-suo-cha-ru-wei-zhi-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    /**
     * 总结:
     * 看过一遍不错的<a href="https://www.cnblogs.com/kyoner/p/11080078.html">博客</a> 但是自己还是没有做出来，主要还是边界问题。
     * 最后还是套用了模板知道个性化的实现。（带入特例就知道返回mid还是返回left了）
     */
}
